//https://leetcode.cn/problems/count-the-repetitions/description/?envType=daily-question&envId=2024-01-02


class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        if (n1 == 0) 
        {
            return 0;
        }
        int s1cnt = 0, index = 0, s2cnt = 0;
        unordered_map<int, pair<int, int>> recall;
        pair<int, int> pre_loop, in_loop;
        while(true)
        {
            ++s1cnt;
            for(char ch : s1)
            {
                if(ch == s2[index])
                {
                    ++index;
                    if(index == s2.size())
                    {
                        ++s2cnt;
                        index = 0;
                    }
                }
            }
            if(s1cnt == n1) return s2cnt / n2;
            if(recall.count(index))
            {
                auto [s1cnt_prime, s2cnt_prime] = recall[index];
                pre_loop = {s1cnt_prime, s2cnt_prime};
                in_loop = {s1cnt - s1cnt_prime, s2cnt - s2cnt_prime};
                break;
            }
            else
            {
                recall[index] = {s1cnt, s2cnt};
            }
        }
        int ans = pre_loop.second + (n1 - pre_loop.first) / in_loop.first * in_loop.second;
        int rest = (n1 - pre_loop.first) % in_loop.first;
        for(int i = 0; i < rest; i++)
        {
            for(char ch :s1)
            {
                if(ch == s2[index])
                {
                    index++;
                    if(index == s2.size())
                    {
                        ans++;
                        index = 0;
                    }
                }
            }
        }

        return ans / n2;
    }
};
